﻿//475. 供暖器
//冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
//在加热器的加热半径范围内的每个房屋都可以获得供暖。
//现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。
//注意：所有供暖器 heaters 都遵循你的半径标准，加热的半径也一样。


class Solution {
public:
    int findRadius(vector<int>& houses, vector<int>& heaters)
    {
        ranges::sort(houses);
        ranges::sort(heaters);
        auto check = [&](int r)->bool
        {
            int m = houses.size();
            int n = heaters.size();
            int j = 0;
            for (int i = 0; i < n; i++)
            {
                long long left = heaters[i] - r;
                long long right = heaters[i] + r;
                while (j < m && houses[j] >= left && houses[j] <= right)
                {
                    j++;
                }
                if (j >= m)
                {
                    return true;
                }
            }
            return false;
        };

        int left = 0, right = INT_MAX;
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (check(mid))
            {
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        }
        return right + 1;
    }
};